/**
 * FileName: DynamicHashST.c
 * --------------------------------------------------------------------
 *
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "../chapter12/ST.h"
#include "../chapter12/Item.h"

static int N; //表中键的数量
static int M; //表中槽位的数量
static Item *st;

//hash函数声明
void init(int);
void expand();
void shrink();
int hash(int);

//符号表操作声明

//hash函数实现
int hash(int x) {
    return (11 * x) % M;
}

void init(int max) {
    int i;
    N = 0;
    M = max;
    st = malloc(M * sizeof(Item));
    for (i = 0; i < M; i++) {
        st[i] = NULLitem;
    }
}

void expand() {
    int i;
    Item *t = st;
    int old_M = M;
    init(M+M);
    for (i = 0; i < old_M; i++) {
        if (t[i] != NULLitem) {
            STinsert(t[i]);
        }
    }
    free(t);
}

void shrink() {
    int i;
    Item *t = st;
    int old_M = M;
    init(M/2);
    for (i = 0; i < old_M; i++) {
        if (t[i] != NULLitem) {
            STinsert(t[i]);
        }
    }
    free(t);
}

// 符号表操作实现
void STinit(int max) {
    init(2 * max);
}

int STcount() {
    return N;
}

/**
 * Program 14.7 Dynamic hash insertion (for linear probing)
 * -------------------------------------------------------------------------------------------------------------------
 * This implementation of `STinsert` for linear probing (see Program 14.4) handles an arbitrary number of keys by
 * doubling the size of the table each time that the table becomes half full.
 *
 * Doubling requires that
 * - we allocate memory for the new table, rehash all the keys into the new table,
 * - then free the memory for the old table.
 *
 * The function `init` is an internal version of `STinit`; the ADT initialization `STinit` can be changed to
 * start the table size M at `4` or any larger value.
 *
 * This same approach can be used for double hashing or separate chaining.
 * -------------------------------------------------------------------------------------------------------------------
 * 动态hash符号表插入操作
 * @param item
 */
void STinsert(Item item) {
    Key v = key(item);
    int i = hash(v);
    while (!null(i)) {
        i = (i+1)%M;
    }
    st[i] = item;
    N++;
    if (N >= M/2) {
        expand();
    }

}

Item STsearch(Key v) {
    int i = hash(v);
    while (!null(i)) {
        if (eq(v, key(st[i]))) {
            return st[i];
        }else {
            i = (i+1)%M;
        }
    }
    return NULLitem;
}

void STdelete(Item item) {
    int j;
    int i = hash(item->key);
    Item v;

    while (!null(i)) {
        if (eq(key(item), key(st[i]))) {
            break;
        }else {
            i = (i+1)%M;
        }
    }
    if (null(i)) {
        return;
    }
    st[i] = NULLitem;
    N--;
    for (j = i + 1; !null(j); j = (j+1)%M, N--) {
        v = st[j];
        st[j] = NULLitem;
        STinsert(v);
    }
    if (N < M/8) {
        shrink();
    }
}